\subsection{Blockcipher-Design}
\label{subsec:Blockcipherdesign}
Dieses Kapitel beschreibt allgemeine Verfahren, die in der Konstruktion moderner Iterierter Blockcipher zur Anwendung kommen. Hierbei werden wir vor allem auf die beiden am weitesten verbreiteten Verfahren, die auf Shannon \cite{ShannonSS} zur\"uckgehenden -- Substitutions-Permutations-Netzwerke und die im Rahmen des Lucifer Projekts \cite{Lucifer} bei IBM entstandenen Feistel-Netzwerke -- eingehen und weitere Ans\"atze kurz beschreiben. Die in den jeweiligen Abschnitten genannten Bausteine werden im n\"achsten Abschnitt genauer be\-schrie\-ben.

\subsubsection{Vorgehen}
\label{subsubsec:Vorgehen}
Verwendet man eines der oben genannten Verfahren, l\"asst sich die Konstruktion eines Blockciphers in die folgenden Schritte aufteilen.
\begin{enumerate}
\item {Design eines Substitutions-Permutations-Netzwerkes oder eines Feistel-\\Netzwerkes.
\begin{itemize}
\item{F\"ur ein Feistel-Netzwerk: Design einer Kernfunktion.}
\end{itemize}}
\item {Design einer oder meherer S(ubstitution)-Boxen.}
\item {Design eines Keyschedule.}
\end{enumerate}

\subsubsection{Grundbegriffe}
\label{subsubsec:Grundbegriffe}
Zun\"achst ben\"otigen wir folgenden Grundbegriffe:
\begin{description}
\item[Kryptosystem:]{Wir betrachten ein Verschl\"usselungs- oder Kryptosystem $KS$ als $5$-Tupel $KS=(\KM,\KC,\KK,\KE,\KD)$ wobei gilt:
\begin{enumerate}
\item {$\KM$ ist die Menge der mit dem System verschl\"usselbaren Klartexte, \textbf{Klartext-} oder \textbf{Plaintextraum}.}
\item {$\KC$ ist die Menge der vom System erzeugbaren Geheimtexte, \textbf{Geheim\-text-} oder \textbf{Ciphertextraum}.}
\item {$\KK$ ist die Menge der zul\"assigen Schl\"ussel des Systems, \textbf{Schl\"usselraum}.}
\item {$\KE$ ist eine Familie $E=(e_{k})_{k\in \KK}$ von Abbildungen $e_{k}:\KM\rightarrow \KC$, den \textbf{Verschl\"usselungsfunktionen} und}
\item {$\KD$ ist eine Familie $D=(d_{k})_{k\in \KK}$ von Abbildungen $d_{k}:C\rightarrow M$, den \textbf{Ent\-schl\"usselungsfunktionen}, so dass gilt:}
\item {$\forall e\in \KE\exists d \in \KD: d(e(m))=m\:f\ddot{u}r\: alle\: m\in \KM$.}
\end{enumerate}}
\item[Endogenes Kryptosystem:] {Ein Kryptosystem, in dem gilt $\KM=\KC$.}
\item[Substitutionscipher:] {Ein Kryptosystem, in dem $\KE$ und $\KD$ Familien von Abbildungen sind, die eine (schl\"usselabh\"angige) Ersetzung des Klartextes vornehmen.}
\item[Permutationscipher:] {Ein Kryptosystem, in dem $\KE$ und $\KD$ Familien von Abbildungen der Form: \begin{equation*}
Permute: \left\{\begin{array}{ll}\Sigma^{n} & \rightarrow \Sigma^{n} \\ (x_0, x_1, \ldots , x_{n-1})&\mapsto(x_{\pi(0)}, x_{\pi(1)}, \ldots , x_{\pi(n-1)})\end{array}\right.
\end{equation*} 
mit $\Sigma$ endliche Menge und 
\begin{equation*}
\pi:\{0,1,2,\ldots , n-1\}\rightarrow \{0,1,2,\ldots , n-1\},\ bijektiv
\end{equation*}
sind. \\
Permutationscipher sind offensichtlich \textit{endogen}.}
\item[Blockcipher:] {Ein Kryptosystem, bei dem gilt: $\KM=\KC=\Sigma^{n},\:n>1, $ sowie $\KK=\Sigma^{m},\:m>1$. Meistens betrachteten wir Algorithmen, in denen gilt: $\Sigma=\{0,1\}$ sowie $n\in\{64,128\}$ und $m\in\{64,128,120,192,256\}$. Die genauen Werte k\"onnen der Tabelle (siehe Anhang \ref{algorithmtables}) entnommen werden.}
\item[Entropie:] {Ma\ss{} f\"ur den mittleren Informationsgehalt eines Zeichens (die Redundanz eines Textes). F\"ur ein Alphabet $Z$ ergibt sich die Entropie als:
\begin{equation*}
H(\Sigma)=-\sum_{m\in\Sigma}p(m)\cdot \log_{2}(p(m))
\end{equation*}
mit $p(m)=P(X=m)$ die Wahrscheinlichkeit, dass das Zeichen $m$ des Alphabets $\Sigma$ auftritt.}
\end{description}

\subsubsection{Konfusion und Diffusion}
\label{subsubsec:confusiondiffusion}
 Wie bereits in \cite{ShannonSS} formuliert sollte ein praktisches Kryptosystem m\"oglichst gute \textbf{Konfusions}- (im englischen Confusion) und \textbf{Diffusions}-Ei\-genschaften aufweisen.
\begin{description}
\item[Diffusion:] {Diffusion bezeichnet die Eigenschaft, dass sich bereits kleine Ver\-\"an\-der\-ungen am Klartext auf den gesamten Geheimtext auswirken. F\"ur die, von uns betrachteten Blockcipher, wird meist angstreb, bei Ver\-\"an\-der\-ung eines Bits des Eingabeblocks, eine Ver\-\"an\-derung von mindestens $50\%$ der Ausgabebits zu erreichen.\\
Auch wenn, wie in \cite{ShannonSS} gezeigte, Diffusion keine Auswirkungen auf die Gesamtentropie (Redundanz) des Geheimtextes hat, wird es einem Angreifer stark erschwert, Zusammenh\"ange zwischen Klar- und Geheimtext, etwa wieder\-kehrende Muster, zu erkennen, da sie sich \"uber we\-sen\-tlich gr\"ossere Teile des Ciphertexts verteilen.}
\item[Konfusion:] {Konfusion bezeichnet die Eigenschaft, dass die \"Anderung eines Schl\"us\-sel\-zeichens Auswirkungen auf den gesamten Geheimtext hat. Wie auch bei Diffusion wird bei Blockciphern angestrebt, eine Ver\"anderung von mindestens $50\%$ der Bits der Ausgabe bei Ver\"anderung eines Bits des Schl\"us\-sels zu erreichen.\\
Konfusion erschwert die Suche nach dem verwendeten Schl\"ussel. Ist kein hoher Grad an Konfusion des Verschl\"usselungsalgorithmus gegeben, sind (Teil)\-Schl\"ussel leicht aus dem Geheimtext erkennbar und k\"onnen zur (Teil)\-Ent\-schl\"us\-selung des Ciphertextes verwendet werden.}
\end{description}
Die m\"oglichst gro\ss{}e Ver\"anderung auf den Ciphertext wird auch als \textbf{Lawinen-} oder \textbf{Avalanche-Effekt} bezeichnet.

\subsubsection{Produktcipher}
\label{subsubsec:productcipher}
Im bereits zitierten Aufsatz stellte Shannon ein Verfahren vor, mit dem effizient Kryptosysteme konstruiert werden k\"onnen, die die oben genannten Eigenschaften besitzen.\\
Wir definieren hierf\"ur das Produkt zweier Kryptosysteme $KS_{1}\times KS_{2}$ als
\begin{eqnarray*}
KS_{1}&=&(\KM,\KM,\KK_{1},\KE_{1},\KD_{1})\\ 
KS_{2}&=&(\KM,\KM,\KK_{2},\KE_{2},\KD_{2})\\
KS_1 \times KS_2 &:=& (\KM,\KM,\KK_{1}\times \KK_{2},\KE_{2}\circ\KE_{1},\KD_{1}\circ\KD_{2})\\
\end{eqnarray*}
Offensichtlich erzeugt das Produkt zweier Kryptosysteme nicht zwangsl\"aufig ein drittes. Beispielsweise l\"asst sich das Produkt zweier Permutationscipher selbst wieder als einfacher Permutationscipher darstellen. Diese Eigenschaft wird als \textbf{Idempotenz} bezeichnet. 

\subsubsection{Substitutions-Permutations-Netzwerke}
\label{subsubsec:spn}
Die von Shannon entwickelten Substitutions-Permutations-Netzwerke sind eine spezielle Form der oben beschriebenen Produktciphern. Durch die folgende Konstruktionsvorschrift werden im Allgemeinen keine idempotenten Cipher erzeugt.\\
Zun\"achst setzten wir voraus, dass alle verwendeten Substitutionscipher $Sub_{i}$ $0\leq i<n$ \textit{endogen} sind, die verwendeten Permutationsschritte $Perm_{i}\ 0\leq i < n-1$ sind wie oben bereits erw\"ahnt endogen. Ist diese Voraussetzung erf\"ullt, lassen sich neue Kryptosysteme erzeugen als:
\begin{equation*}
KS=Sub_{0}\times Perm_{0}\times \ldots\times Perm_{n-2} \times Sub_{n-1}
\end{equation*}
Da Substitutions- und Permutationsschritte in alternierender Abfolge verwendet werden, kann nur in wenigen F\"allen, in denen sich alle Substitutions- bzw. Permutationsschritte gegenseitig aufheben, ein idempotenter Cipher entstehen.\\
Im allgemeinen werden in modernen Blockciphern Substitutions-Per\-mu\-ta\-tions-Netzwerke eingesetzt die sich als wiederholte Anwendung von wenigen gleichen Substitutions- und Permutationsschritten darstellen lassen also Produktcipher der Form:
\begin{equation*}
KS=(Sub_{0}\times Perm_{0} \times Sub_{1} \times Perm_{1} \times \ldots Sub_{n-2} \times Perm_{n-2})^{m}\times Sub_{n-1}
\end{equation*}
Der bekannteste Vertreter eines Substitutions-Permutations-Netzwerk ist der Rijndael Algorithmus \cite{Rijndael}, der im Oktober 2000 als Nachfolger f\"ur DES bzw. Triple-DES vom National Institute of Standards and Technology bekanntgegeben wurde.

\subsubsection{Feistel-Netzwerke}
\label{subsubsec:feistel}
Den zweiten wichtigen Ansatz zur Konstruktion von Blockciphern bilden Feistelnetzwerke. Diese wurden von Horst Feistel im Rahmen des Luciferprojektes bei IBM entwickelt.\\
Feistelnetzwerke funktionieren nach folgendem grundlegenden Prinzip:\\
F\"ur $n$ Wiederholungen (Runden):
\begin{enumerate}
\item {Teile den Eingabeblock in Teilbl\"ocke (zumeist zwei Teilbl\"ocke gleicher Gr\"o\ss{}e) auf.}
\item {Vertausche die Blockreihenfolge.}
\item {Wende eine Kernfunktion (siehe unten) auf einen Teilblock oder mehrere Teilbl\"ocke und einen Rundenschl\"ussel (siehe unten) an.}
\item {Verkn\"upfe ($xor,\ modulare Addition,\ \ldots$) die bearbeiteten mit den unbearbeiteten Teilbl\"ocken.}
\item {Erzeuge als Ausgabe die Konkatenation der bearbeiteten und der unbearbeiteten Teilbl\"ocke.}
\end{enumerate}
Feistelnetzwerke bieten den Vorteil, dass zur Entschl\"usselung die Inverse der Kernfunktion nicht bekannt sein muss, bzw. nicht existieren muss. Weiter unterscheiden sich die Ver- und Endschl\"usselungsfunktion nur durch die Reihenfolge, in der die Rundenschl\"ussel verwendet werden.\\
Der bekannteste Vertreter eines Feistelnetzwerkes ist der DES-Algorithmus, der als Nachfolger von Lucifer II bei IBM entwickelt und 1976 vom FIPS zum Standardverschl\"usselungverfahren der US-Regierung gew\"ahlt wurde.
\subsubsection{Kernfunktion}
\label{subsubsec:kernfunktion}
Die Kernfunktion eines Feistelnetzwerkes kann in den meisten F\"allen als einrundiges (schl\"usselabh\"angiges) Substitutions-Permutations-Netzwerk aufgefasst werden. Neben Substitutions- und Permutationsschritten werden allerdings, vor allem in aktuelleren Algorithmen, auch vermehrt modlar-arith\-me\-tische Operationen auf den Eingabeblock angewendet.

\subsubsection{S(ubstitutions)-Box}
\label{subsubsec:sbox2}
Neben der Konstruktion der linearen Abbildungen (Permutationen und arithmetischen Operationen), m\"ussen bei modernen Blockciphern zwei weitere Bausteine entwickelt werden, S-Boxen und ein Keyschedule.\\
Zun\"achst S-Boxen: S- oder Substitutions-Boxen sind die oben genannten Substitutionsschritte, werden also sowohl in SP- als auch in Feistel-Netzwerken verwendet. Bei ihrer Entwicklung m\"ussen zwei Kriterien erf\"ullt sein:
\begin{enumerate}
\item {Die Substitution darf nicht linear sein. Eine lineare S-Box macht den Blockcipher anf\"allig f\"ur lineare Kryptoanalyse \cite {linearcryptoanalysis}.}
\item {Es darf keine Abh\"angigkeit der einzelnen S-Box-Elemente untereinander geben. Wird dieses Designziel verfehlt, wird der resultierende Cipher anf
\-\"al\-lig f\"ur differenzielle Kryptoanalyse \cite{differentialcryptoanalysis}.} 
\end{enumerate}
Die Entwicklung von S-Boxen, die oben genannte Anforderungen erf\"ullen, ist keine triviale Aufgabe. Zu ihrer L\"osung werden unterschiedliche Ans\"atze verfolgt.
\begin{description}
\item[Zuf\"allig gew\"ahlte S-Boxen:]{Kleine zuf\"allig gew\"ahlte S-Box\-en erf\"ullen die oben genannten Anforderungen mit gro\ss{}er Wahrscheinlichkeit nicht, werden allerdings gro\ss{}e S-Boxen zuf\"allig gew\"ahlt, steigt die Wahrscheinlichkeit, dass die Anforderungen erf\"ullt sind oder zumindest kein trivialer Zusammenhang entsteht. Dieser Ansatz wird etwa in \cite{bigrandomsboxes1} und \cite{bigrandomsboxes2} verfolgt.}
\item[Zuf\"alliges W\"ahlen und \"Uberpr\"ufen:]{Neben der M\"oglichkeit, gro\ss{}e S-Box\-en zu w\"ahlen, lassen sich auch kleine zuf\"allig erzeugen, auf die oben genannten Eigenschaften pr\"ufen und gegebenenfalls verwerfen. Siehe \cite{chooseandtest1} und \cite{chooseandtest2}.}
\item[Handerzeugt:]{Bart Preneel stellte in seiner Doktorarbeit Kriterien zum manuellen Erzeugen von S-Boxen vor \cite{manmade}.}
\item[Erzeugung nach mathematische Schemata:]{Zur Zeit am h\"aufigsten verwendet werden S-Boxen, die nach einem mathematischen Schema konstruiert werden wie beispielsweise in \cite{mathmade} und \cite {Rijndael} beschrieben.}
\item[Schl\"usselabh\"angige S-Boxen:] {
Neben den festen Look-up-Tabellen die durch die oben beschriebenen Verfahren erzeugt werden, werden in aktuellen Kryptoalgorithmen auch vermehrt die von Bruce Schneier propagierten schl\"ussel\-abh\"angigen S-Boxen verwendet. Hierbei werden zun\"achst nach einem der oben genannten Verfahren S-Boxen erzeugt, nach Festlegen des Schl\"ussels werden die S-Boxen dann anhand eines SP-Netzwerkes trans\-for\-miert. }
\end{description}

\subsubsection{Keyschedule}
\label{subsubsec:keyschedule}
Sowohl in Feistel- als auch in Substitutions-Permutations-Netzwerken werden in den einzelnen Runden Schl\"ussel mit dem Klartext verkn\"upft, meistens mittels $xor$ oder $modularer Addition$ oder es werden schl\"us\-sel\-ab\-h\"ang\-ige Permtationen oder Substitutionen verwendet.\\
Diese Schl\"ussel bilden neben dem Klartext die einzigen ver\"anderlichen Parameter der einzelnen Runden. Hieraus ergibt sich die Not\-wen\-dig\-keit, sofern m\"oglich, in jeder Runde unterschiedliche Schl\"ussel zu verwenden. Es sollte also m\"oglichst viel Schl\"usselmaterial vorliegen. Demgegen\"uber steht die Anforderung, dass der Schl\"ussel m\"oglichst einfach gespeichert werden soll.\\
Diese beiden Anforderungen machen die Entwicklung eines Keyschedules not\-wendig. Hierbei werden aus einem relativ kurzen Schl\"ussel durch Anwendung von Transformationen weitere sogenannte \textbf{Rundensch\"ussel} gewonnen.\\
In den von uns betrachteten Blockciphern sind diese Transformationen bereits von sehr unterschiedlicher Komplexit\"at. In TEA wird der 128-Bit-Schl\"ussel nur in vier 32-Bit-Schl\"ussel geteilt, die wiederholt verwendet werden. Demgegen\"uber wird bei Blowfish und TWOFISH der Verschl\"usselungsalgorithmus selbst wiederholt auf den Schl\"ussel angewendet und so werden nur f\"ur die Schl\"usselerzugung bereits 4 KB Daten verschl\"usselt.\\
Auch wenn die bereits bei S-Boxen geforderten Eigenschaften auch bei Key\-schedules von grosser Bedeutung zur Absicherung gegen lineare und differenzielle Kryptoanalyse \cite{Keyschedule} sind, existieren hier noch keine Verfahrensmodelle, die zur Entwicklung herangezogen werden k\"onnten. 


\subsubsection{Weitere Verfahren}
Neben den beiden oben genannten Ans\"atzen zur Konstruktion von Blockciphern gibt es eine Reihe weiterer, die allerdings bisher nur selten verwendet wurden.\\
In \cite{chaoticmaps} stellen die Autoren einen Verschl\"usselungsalgorithmus vor, der auf der Iteration von Chaotic Maps basiert. Dieser Algorithmus ist nicht sicher \cite{chaoticmapsinsecure}.\\
Weiter gibt es zahlreiche Algorithmen, die auf der Verwendung von fehlerkorrigierenden Codes basieren, vor allem \cite{ECC} und davon abgeleitete.\\
Au"serdem lassen sich Kryptoalgorithmen aus kryptographischen Hashfunktionen erzeugen, siehe dazu \cite{appliedcryptography}.
